package linkedlist.test234;

import listbyorder.utils.ListNode;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/15 12:38
 */
public class Solution1 {

    // 反转回文链表（头尾比较）
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        // 快慢指针找到中间节点
        ListNode s = head, f = head;
        while (f.next != null && f.next.next != null) {
            s = s.next;
            f = f.next.next;
        }
        ListNode c = s.next;
        s = null;
        while (c != null) {
            f = c.next;
            c.next = s;
            s = c;
            c = f;
        }
        // s为反转后的头节点
        c = s;
        f = head;
        boolean flag = true;
        while (s != null && f != null) {
            if (s.val != f.val) {
                flag = false;
                break;
            }
            s = s.next;
            f = f.next;
        }
        // 反转回来
        s = null;
        while (c != null) {
            f = c.next;
            c.next = s;
            s = c;
            c = f;
        }
        return flag;
    }
}
